package com.sourcetrip.raw.model;

/**
 * @author: ZhouBert
 * @date: 2020/12/1
 * @description:
 */
public class MyAVLNode<E> extends MyBinaryNode<E> {

	/**
	 * 记录 本节点的 高度
	 * 从下至上
	 */
	protected int height;

	/**
	 * 平衡因子 - 放在方法里进行返回
	 */
	//protected int balanceFactor;
	public int getHeight() {
		return height;
	}

	public void setHeight(int height) {
		this.height = height;
	}


	/**
	 * constructor
	 *
	 * @param element
	 * @param parent
	 */
	public MyAVLNode(E element, MyBinaryNode<E> parent) {
		super(element, parent);
	}

	/**
	 * constructor (including height)
	 *
	 * @param element
	 * @param parent
	 * @param height
	 */
	public MyAVLNode(E element, MyBinaryNode<E> parent, int height) {
		super(element, parent);
		this.height = height;
	}

	/**
	 * 判断本节点是否失衡
	 * 绝对值小于等于 1 -> 平衡
	 *
	 * @return
	 */
	public boolean isBalance() {
		return Math.abs(balanceFactor()) <= 1;
	}

	/**
	 * 返回本节点的平衡因子
	 * 既然进的来这个方法，this != null
	 *
	 * @return
	 */
	public int balanceFactor() {
		//1.获取左子树的高度
		int leftHeight = this.left == null ? 0 : ((MyAVLNode) this.left).height;
		int rightHeight = this.right == null ? 0 : ((MyAVLNode) this.right).height;
		//2.计算
		return leftHeight - rightHeight;
	}

	/**
	 * 更新本节点的高度
	 */
	public void updateHeight() {
		int leftHeight = this.left == null ? 0 : ((MyAVLNode) this.left).height;
		int rightHeight = this.right == null ? 0 : ((MyAVLNode) this.right).height;
		height = Math.max(leftHeight, rightHeight) + 1;
	}

	/**
	 * 返回当前节点的最长子树
	 * 如果 子树高度相等，那么返回跟父节点同向节点！
	 *
	 * @return
	 */
	public MyAVLNode getTallerChild() {
		int leftHeight = this.left == null ? 0 : ((MyAVLNode) this.left).height;
		int rightHeight = this.right == null ? 0 : ((MyAVLNode) this.right).height;
		if (leftHeight > rightHeight) {
			return (MyAVLNode) this.left;
		} else if (leftHeight < rightHeight) {
			return (MyAVLNode) this.right;
		} else {
			return isLeftChild() ? (MyAVLNode) this.left : (MyAVLNode) this.right;
		}
	}

	@Override
	public String toString() {
		if (element == null) {
			return "";
		}
		return element.toString() + "_(p-" + ((parent == null || parent.getElement() == null) ? "" : parent.getElement()) + ";h-" + height + ")";
	}
}
